package cn.zzf.algs.note.exercise.fundamental;

import edu.princeton.cs.algs4.StdOut;

import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * @author GaoFeng
 * @date 2019/11/25 12:20
 */
public class Ex1_1_29 {

    public static void main(String[] args) {
        int size = 100;
        Integer[] nums = IntStream.rangeClosed(1, size)
                .sequential().boxed().toArray(Integer[]::new);

        // 打印数组
        StdOut.println(Arrays.toString(nums));

        // 寻找元素并返有多少个小于它的
        int index = binarySearch(nums, 101, 0, size - 1);
        StdOut.println(index);

        // 寻找元素，并返回有多少个与之相等的
        index = count(nums, 99);
        StdOut.println(index);
    }

    public static  <T extends Comparable<T>> int binarySearch(T[] array, T element, int begin, int end) {

        int mid = (begin + end) / 2;

        if (begin > end) {
            return Math.max(-1, end + 1);
        }
        
        if (element.compareTo(array[mid]) > 0) {
            // 比当前元素大往右找
            return binarySearch(array, element, mid + 1, end);
        } else if ( element.compareTo(array[mid]) < 0) {
            // 比当前元素往左找
            return binarySearch(array, element, begin, mid - 1);
        } else {
            return mid;
        }

    }

    public static <T extends Comparable<T>> int rank(T[] array, T element) {
        return binarySearch(array, element, 0, array.length);
    }

    public static <T extends  Comparable<T>> int count(T[] array, T element) {
        int index = binarySearch(array, element, 0, array.length - 1);

        if (index < 0 || index >= array.length) {
            return 0;
        }

        int count = 1;

        // 左边相等的
        for (int i = index - 1;i > 0;i--) {
            if (array[i].compareTo(element) == 0) {
                count++;
            } else {
                break;
            }
        }

        for (int i = index + 1;i < array.length;i++) {
            if (array[i].compareTo(element) == 0) {
                count++;
            } else {
                break;
            }
        }

        return count;

    }

    /*public static <T extends Comparable<T>> int rank(T[] array, T element) {
        //
    }

    public static int count() {

    }*/


}
